\begin{usection}{10003. Cutting sticks}
	\url{http://uva.onlinejudge.org/external/100/10003.html}\\
	
	Dado un palo de cierta longitud y un conjunto de longitudes a las que hay que cortar el palo, encontrar la secuencia de cortes que minimice el costo. Cortar un palo cuesta la longitud del palo que se está cortando.
			
	\begin{usubsection}{Idea}
		Este problema puede pensarse como una función recursiva. El costo para cortar un palo empezando por el corte $i$ es el costo de cortarlo, más el costo de hacer todos los cortes de cada mitad.
		El mínimo costo se encuentra buscando el $i$ que minimice el costo de cortar cada mitad. Encontramos el mínimo costo de cortar cada mitad recursivamente. En este sentido la solución se parece a una de Divide\&Conquer.
		
		Al calcular función recursiva nos encontramos con muchos subproblemas superpuestos, y tiene un dominio de $n\times n$. Esto es muy apropiado para u\-sar la técnica de Programación Dinámica, que almacena los resultados de la función a medida que los calcula.\\
			
		La función que da el costo mínimo para cortar el segmento $(from,to)$ es:
		$$\texttt{costo}(from,to) = (to-from)+\min_{i\in \texttt{cortes}(from,to)}(\texttt{costo}(from, i)+\texttt{costo}(i,to))$$
		donde \texttt{cortes}$(from,to)$ es el conjunto de cortes que hay que hacer entre $from$ y $to$\footnote{$from$ y $to$ son distancias a las que hay que hacer un corte}.
	\end{usubsection}
		
	\begin{usubsection}{Complejidad}
		El dominio de la función es de $n\times n$, entonces podemos guardar en una matriz de $n\times n$ los resultados de la función cada vez que la llamamos. La función $\texttt{costo}(0,longitud)$ resuelve el problema.
			
		Cada instancia de la función $\texttt{costo}(from,to)$ requiere del resultado de $\texttt{costo}(from,i)$ y de $\texttt{costo}(i,to)$ $\forall i\in \texttt{cortes}(from,to)$.
			
		Si una una instancia ya fue resuelta se devuelve el resultado en \Ode{1}, sino se resuelve llamando a otras $2n$ instancias.
		En el peor caso se calcula la función para todo el dominio. Entonces la conplejidad es de $(n\times n)\times 2n \in \Ode{n^3}$
	\end{usubsection}
\end{usection}

